package 力扣._100033_最大合金数;

import java.util.ArrayList;
import java.util.List;

public class Solution2 {
    public int maxNumberOfAlloys(int n, int k, int budget, List<List<Integer>> composition, List<Integer> stock, List<Integer> cost) {
        //对每台机器分别计算其能生产的最多合金
        int max_fen = -1;
        for (int i = 0; i < k; i++) {
            List<Integer> needs = composition.get(i); //一次所需合金
            int money = 0;
            //按照仓库的数量，生产一份数需要多少钱
            for (int j = 0; j < n; j++) {
                money += cost.get(j) * needs.get(j);
            }
            int l_fen = budget / money; //最小
            int r_fen = 0; //最大份数
            for (int j = 0; j < n; j++) {
                int t = (stock.get(j) + budget / cost.get(j)) / needs.get(j);
                r_fen = Math.max(r_fen, t);
            }
            int mid;
            int max = l_fen;
            //可以二分整
            while (l_fen <= r_fen) {
                mid = (l_fen + r_fen) / 2;
                int need_money = 0;
                for (int l = 0; l < n; l++) {
//                    need_money += Math.max(0, mid - stock.get(l) / needs.get(l)) * cost.get(l) * needs.get(l);
                    need_money += Math.max(0, mid * needs.get(l) - stock.get(l)) * cost.get(l);
                }
                if (need_money > budget)
                    r_fen = mid - 1;
                else {
                    l_fen = mid + 1;
                    max = Math.max(max, mid);
                }
            }
            max_fen = Math.max(max, max_fen);
        }
        return max_fen;
    }

    public static void main(String[] args) {
        int n = 4;
        int k = 4;
        int bug = 17;
        List<List<Integer>> composition = new ArrayList<>();

        List<Integer> t1 = new ArrayList<>();
        t1.add(10);
        t1.add(10);
        t1.add(1);
        t1.add(5);
        List<Integer> t2 = new ArrayList<>();
        t2.add(9);
        t2.add(7);
        t2.add(7);
        t2.add(1);
        List<Integer> t3 = new ArrayList<>();
        t3.add(6);
        t3.add(3);
        t3.add(5);
        t3.add(9);
        List<Integer> t4 = new ArrayList<>();
        t4.add(2);
        t4.add(10);
        t4.add(2);
        t4.add(7);
        composition.add(t1);
        composition.add(t2);
        composition.add(t3);
        composition.add(t4);

        List<Integer> stock = new ArrayList<>();
        stock.add(9);
        stock.add(8);
        stock.add(2);
        stock.add(7);
        List<Integer> cost = new ArrayList<>();
        cost.add(9);
        cost.add(2);
        cost.add(6);
        cost.add(10);

        int i = new Solution2().maxNumberOfAlloys(n, k, bug, composition, stock, cost);
        System.out.println(i);
    }

}
